package com.kevinkk.dp;

/**
 * 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
 * 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。
 * 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
 * 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
 */

/**
 * 1. dp 数组含义：dp[0] 表示偷这个节点获得的金额，dp[1] 表示不偷
 * 2. dp 公式：
 *      偷这个节点，那么其孩子节点都不能偷：res[0] = root.val + left[1] + right[1]
 *      不偷这个节点，那么获得的最大金额就是其左右孩子的最大值之和：res[1] = max(left[0], left[1]) + Math.max(right[0], right[1])
 *      注意可以同时偷一个节点的两个孩子
 *      在递归遍历二叉树时，递归的过程会自动记录下遍历的中间结果
 * 3. 初始化
 * 4. 遍历顺序：采取后序遍历
 */

public class HouseRobberIII {
    class Solution {
        public int rob(TreeNode root) {
            int[] res = traversal(root);
            return Math.max(res[0], res[1]);
        }

        private int[] traversal(TreeNode root){
            int[] res = new int[2];
            if(root == null) return res;

            int[] left = traversal(root.left);
            int[] right = traversal(root.right);

            res[0] = root.val + left[1] + right[1];
            res[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

            return res;
        }
    }
}
